/* 判断给定二叉树是否是二叉(搜索)排序树 */

#include <iostream>
#include "BiTree.h"
using namespace std;

// 记录前一个值，默认为负无穷大
int pre = -INT_MAX;

// 判断是否为二叉排序树
int JudgeBST(BTNode *root)
{
  // 二叉树为空
  if (root == NULL)
    return 1;
  
  // 左子树是二叉排序树
  int a = JudgeBST(root->lchild);
  
  // 左子树不是二叉排序树 或者 前一个值不小于根结点记录的值
  if (root->data <= pre || a == 0)
    return 0; // 不是二叉排序树
  else
    pre = root->data; // 更新前一个值
  
  // 右子树是二叉排序树
  int b = JudgeBST(root->rchild);
  
  // 返回结果
  return b;
}

int main()
{
  // 创建二叉树
  BTNode *T = create_BiTree();
  
  // 判断是否为二叉排序树
  if (JudgeBST(T))
    cout << "是二叉排序树!";
  else
    cout << "不是二叉排序树!";
  return 0;
}
